// Copyright (C) 2011  Andrew H. Chan
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

#ifndef _GRAPH_H__
#define _GRAPH_H__

#include "typedefs.h"
#include "util.h"

template<typename VertexT, typename EdgeT, typename GraphDataT>
class Graph {
    public:
        typedef VertexT vertex_type;
        typedef EdgeT edge_type;
        typedef GraphDataT graph_data_type;

        typedef std::vector<std::pair<uint,uint> > edge_list;
        typedef std::pair<edge_list, edge_list> edge_lists;
        typedef boost::unordered_map<uint, edge_lists> adj_list;

        // vertex maps
        typedef boost::unordered_map<VertexT, uint> v_to_id;
        typedef boost::unordered_map<uint, VertexT> id_to_v;

        // edge maps
        typedef boost::unordered_map<uint, EdgeT> id_to_e;
        typedef boost::unordered_map<uint, std::pair<uint, uint> > id_to_vv;
        typedef boost::unordered_map<std::pair<uint,uint>, std::vector<uint> > vv_to_ids;

        Graph();
        // returns (vertex ID, vertex added?)
        std::pair<uint, bool> add_vertex(VertexT const& vert);
        // returns edge ID
        uint add_edge(VertexT const& vert1, VertexT const& vert2, EdgeT const& edge_data = EdgeT());

        uint add_edge(uint const& vert1, uint const& vert2, EdgeT const& edge_data = EdgeT());

        void remove_edge(uint eid);

        uint num_edges() const;
        uint num_vertices() const;

        void clear();

        // 0: at most one edge between u,v
        // 1: more than one edge for some u,v
        int check_multiedge() const;

        // garbage collect
        void gc();

        edge_list& outedges(VertexT const& vert);
        edge_list const& outedges(VertexT const& vert) const;

        edge_list& outedges(uint const& vid);
        edge_list const& outedges(uint const& vid) const;

        edge_list& inedges(VertexT const& vert);
        edge_list const& inedges(VertexT const& vert) const;

        edge_list& inedges(uint const& vid);
        edge_list const& inedges(uint const& vid) const;

        // data members
        adj_list adj; // adjacency list

        v_to_id vtoid; // vertex label to vertex id
        id_to_v idtov; // vertex id to vertex label

        id_to_e idtoe; // edge id to edge data
        id_to_vv idtovv; // edge id to incident vertices
        vv_to_ids vvtoids; // incident vertices to edge id

        GraphDataT graph_data;

    private:
        uint vid;
        uint eid;
};

template<typename VertexT, typename EdgeT, typename GraphDataT>
Graph<VertexT, EdgeT, GraphDataT>::Graph() : vid(0), eid(0) {}

// returns vertex id of the vertex added 
//    if vertex already exists, returns vertex id of existing vertex
// returns true if vertex is added, false otherwise
template<typename VertexT, typename EdgeT, typename GraphDataT>
std::pair<uint, bool> Graph<VertexT, EdgeT, GraphDataT>::add_vertex(VertexT const& vert) {
    if(vtoid.find(vert) == vtoid.end()) {
        vtoid[vert] = vid;
        idtov[vid] = vert;
        adj[vid].first = edge_list();
        adj[vid].second = edge_list();
        ++vid;
        return std::pair<uint, bool>(vid-1, true);
    } else {
        return std::pair<uint, bool>(vtoid[vert], false);
    }
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
uint Graph<VertexT, EdgeT, GraphDataT>::add_edge(VertexT const& vert1, VertexT const& vert2, EdgeT const& edge_data) {
    // check if vertices exist
    if(vtoid.find(vert1) == vtoid.end() || vtoid.find(vert2) == vtoid.end()) {
        // no where in this program should you try to add an edge when the vertices don't exist, so assert(false)
        assert(false); 
        return false;
    }

    uint vid1 = vtoid[vert1];
    uint vid2 = vtoid[vert2];

    // add out edge
    edge_list &cur_outedge = adj[vid1].first;
    cur_outedge.push_back(std::pair<uint,uint>(vid2, eid));

    // add in edge
    edge_list &cur_inedge = adj[vid2].second;
    cur_inedge.push_back(std::pair<uint,uint>(vid1, eid));

    // map edge ID to edge data
    idtoe[eid] = edge_data; 
    // map edge ID to vertex pair (uv)
    idtovv[eid] = std::pair<uint,uint>(vid1,vid2);
    // map vertex pair (u,v) to vector of edge ids (multigraph)
    vvtoids[std::pair<uint,uint>(vid1,vid2)].push_back(eid);

    ++eid;

    return eid - 1;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
uint Graph<VertexT, EdgeT, GraphDataT>::add_edge(uint const& vid1, uint const& vid2, EdgeT const& edge_data) {
    // check if vertices exist
    if(adj.find(vid1) == adj.end() || adj.find(vid1) == adj.end()) {
        // no where in this program should you try to add an edge when the vertices don't exist, so assert(false)
        assert(false); 
        return false;
    }

    // add out edge
    edge_list &cur_outedge = adj[vid1].first;
    cur_outedge.push_back(std::pair<uint,uint>(vid2, eid));

    // add in edge
    edge_list &cur_inedge = adj[vid2].second;
    cur_inedge.push_back(std::pair<uint,uint>(vid1, eid));

    // map edge ID to edge data
    idtoe[eid] = edge_data; 
    // map edge ID to vertex pair (uv)
    idtovv[eid] = std::pair<uint,uint>(vid1,vid2);
    // map vertex pair (u,v) to vector of edge ids (multigraph)
    vvtoids[std::pair<uint,uint>(vid1,vid2)].push_back(eid);

    ++eid;

    return eid - 1;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
void Graph<VertexT, EdgeT, GraphDataT>::remove_edge(uint eid) {
    if(idtovv.find(eid) == idtovv.end()) {
        assert(false);
        return;
    }

    std::pair<uint, uint> vv = idtovv.at(eid);
    uint vid1 = vv.first;
    uint vid2 = vv.second;

    // remove out edge
    edge_list &cur_outedge = adj[vid1].first;
    for(edge_list::iterator iter = cur_outedge.begin(); iter != cur_outedge.end(); ++iter) {
        if(iter->second == eid) {
            cur_outedge.erase(iter);
            break;
        }
    }

    // remove in edge
    edge_list &cur_inedge = adj[vid2].second;
    for(edge_list::iterator iter = cur_inedge.begin(); iter != cur_inedge.end(); ++iter) {
        if(iter->second == eid) {
            cur_inedge.erase(iter);
            break;
        }
    }

    // remove edge ID from edge data hash
    idtoe.erase(eid);
    // remove edge ID from id to vertex pair hash
    idtovv.erase(eid);
    // remove edge from vertex pair to ids hash
    vv_to_ids::iterator vertex_pair = vvtoids.find(vv);
    for(std::vector<uint>::iterator iter = vertex_pair->second.begin(); iter != vertex_pair->second.end(); ++iter) {
        if(*iter == eid) {
            vertex_pair->second.erase(iter);
            break;
        }
    }
    if(vertex_pair->second.size() == 0) {
        vvtoids.erase(vertex_pair);
    }
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
uint Graph<VertexT, EdgeT, GraphDataT>::num_edges() const {
    return idtoe.size(); 
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
uint Graph<VertexT, EdgeT, GraphDataT>::num_vertices() const {
    return adj.size(); 
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
typename Graph<VertexT, EdgeT, GraphDataT>::edge_list& Graph<VertexT, EdgeT, GraphDataT>::outedges(VertexT const& vert) {
    return adj(vtoid.at(vert)).first;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
typename Graph<VertexT, EdgeT, GraphDataT>::edge_list const& Graph<VertexT, EdgeT, GraphDataT>::outedges(VertexT const& vert) const {
    return adj.at(vtoid.at(vert)).first;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
typename Graph<VertexT, EdgeT, GraphDataT>::edge_list& Graph<VertexT, EdgeT, GraphDataT>::outedges(uint const& vid) {
    return adj.at(vid).first;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
typename Graph<VertexT, EdgeT, GraphDataT>::edge_list const& Graph<VertexT, EdgeT, GraphDataT>::outedges(uint const& vid) const {
    return adj.at(vid).first;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
typename Graph<VertexT, EdgeT, GraphDataT>::edge_list& Graph<VertexT, EdgeT, GraphDataT>::inedges(VertexT const& vert) {
    return adj.at(vtoid.at(vert)).second;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
typename Graph<VertexT, EdgeT, GraphDataT>::edge_list const& Graph<VertexT, EdgeT, GraphDataT>::inedges(VertexT const& vert) const {
    return adj.at(vtoid.at(vert)).second;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
typename Graph<VertexT, EdgeT, GraphDataT>::edge_list& Graph<VertexT, EdgeT, GraphDataT>::inedges(uint const& vid) {
    return adj.at(vid).second;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
typename Graph<VertexT, EdgeT, GraphDataT>::edge_list const& Graph<VertexT, EdgeT, GraphDataT>::inedges(uint const& vid) const {
    return adj.at(vid).second;
}

template<typename VertexT, typename EdgeT, typename GraphDataT>
void Graph<VertexT, EdgeT, GraphDataT>::clear() {
    adj.clear();
    vtoid.clear();
    idtov.clear();
    idtovv.clear();
    vvtoids.clear();
    idtoe.clear();
}

// return value
// 0: at most one edge between any pair of vertices
// 1: more than one edge between some pair of vertices
template<typename VertexT, typename EdgeT, typename GraphDataT>
int Graph<VertexT, EdgeT, GraphDataT>::check_multiedge() const {
    int multiedge = 0;
    for(vv_to_ids::const_iterator piter = vvtoids.begin(); piter != vvtoids.end(); ++piter) {
        if(piter->second.size() > 1) {
            multiedge = 1;
            break;
        }
    }
    return multiedge;
}

#endif
